#include<stdio.h>
#include<stdlib.h>

struct Node
 {
         int val;
         struct Node *next;
        struct Node *random;
};


struct Node* copyRandomList(struct Node* head)
{
    if(head==NULL)
        return NULL;
    //临时拷贝
    struct Node* cur=head;
    while(cur)
    {
        struct Node* next=cur->next;
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        cur->next=copy;
        copy->next=next;
        copy->val=cur->val;
        cur=next;
    }
    //置random
     cur=head;
    while(cur)
    {
        struct Node* next =cur->next;
        if(cur->random!=NULL)
        {next->random=cur->random->next;}
        else
        { next->random=NULL;}
        cur=cur->next->next;
    }
    //拆分
    struct Node* newhead=(struct Node*)malloc(sizeof(struct Node));
    struct Node* tail=newhead;
     cur=head;
    while(cur)
    {
        tail->next=cur->next;
        tail=tail->next;
        cur=cur->next->next;
    }

    //返回
    struct Node* returnhead=newhead->next;
    free(newhead);
    return returnhead;
}
int main()
{
    struct Node * list=NULL;
    struct Node *n1= (struct Node*)malloc(sizeof(struct Node));
    struct Node* n2= (struct Node*)malloc(sizeof(struct Node));
    struct Node *n3= (struct Node*)malloc(sizeof(struct Node));

    list=n1;
    n1->val=3;
    n2->val=4;
    n3->val=5;

    n1->next=n2;
    n2->next=n3;
    n3->next=NULL;

    n1->random=n3;
    n2->random=n1;
    n3->random=NULL;

    struct Node *ret=copyRandomList(list);

    return 0;
}